﻿using System;
using Algoritmia.Utils;
using Lists = Algoritmia.DataStructures.Lists;

namespace Algoritmia.Problems.Geometry.ConvexMin
{
    public class IterativeConvexMinFinder<T> : IConvexSequenceMinFinder<T>
    {
        private readonly Comparison<T> _comparison;

        public IterativeConvexMinFinder(Comparison<T> comparison = null)
        {
            _comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);
        }

        #region Implementation of IConvexSequenceMinFinder<T>

        public T Min(Lists.IList<T> list)
        {
            int i = 0, k = list.Count;
            while (k - i > 2)
            {
                int j = (i + k)/2;
                if (_comparison(list[j - 1], list[j]) < 0)
                {
                    k = j;
                }
                else
                {
                    i = j;
                }
            }
            return k - i == 1 ? list[i] : _comparison(list[i], list[i + 1]) < 0 ? list[i] : list[i + 1];
        }

        #endregion
    }
}
